package com.zk.algorithm.string;

import com.zk.algorithm.annotation.Finished;
import com.zk.algorithm.annotation.Hard;
import com.zk.algorithm.annotation.LeetCode;
import com.zk.algorithm.annotation.TiaoZhanChengXuSheJiJingSai;

import java.util.HashMap;

/**
 * 包含一个字符串的所有字符的最小 substring
 *
 * Input: S = "ADOBECODEBANC", T = "ABC"
   Output: "BANC"
 *
 * @author zk
 */
@LeetCode("76")
@Finished(false)
@Hard
@TiaoZhanChengXuSheJiJingSai("读书任务-知识点覆盖")
public class MinimumWindowSubstring {

    public static void main(String[] args) {
        System.out.println(new MinimumWindowSubstring().minWindow("ADOBECODEBANC", "ABC"));
    }

    public String minWindow(String s, String t) {
        if (s == null || s.length() < t.length() || s.length() == 0) {
            return "";
        }

        // ======================
        // 字符串 t 的所有字符统计
        // ======================
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (char c : t.toCharArray()) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }

        // ======================
        // begin      end
        // ↓___________↓______
        // ======================
        int left = 0;
        int minLeft = 0;
        int minLen = s.length() + 1;
        int count = 0;

        for (int right = 0; right < s.length(); right++) {
            // ======================
            // end ---> 寻找位置
            // ↓_________________
            // ======================
            char rightChar = s.charAt(right);
            if (map.containsKey(rightChar)) {
                map.put(rightChar, map.get(rightChar) - 1);
                if (map.get(rightChar) >= 0) {
                    count++;
                }

                // ======================
                // begin -->  end (已经确定)
                // ↓___________↓______
                //
                // 尝试把 begin 向后移动，缩短范围
                // ======================
                while (count == t.length()) {

                    // ======================
                    // 新的距离
                    // ======================
                    if (right - left + 1 < minLen) {
                        minLeft = left;
                        minLen = right - left + 1;
                    }

                    // ======================
                    // 让 begin 和 end 中间的字符串不合法
                    // ======================
                    char leftChar = s.charAt(left);
                    if (map.containsKey(leftChar)) {

                        map.put(leftChar, map.get(leftChar) + 1);
                        if (map.get(leftChar) > 0) {
                            count--;
                        }

                    }

                    left++;
                }
            }
        }

        if (minLen > s.length()) {
            return "";
        }

        return s.substring(minLeft, minLeft + minLen);
    }

}